//
//  BinaryTreePaths.swift
//  LeetCodeSummary
//
//  Created by WangYonghe on 2020/9/4.
//  Copyright © 2020 WangYonghe. All rights reserved.
//  257. 二叉树的所有路径

import UIKit

/*
 257. 二叉树的所有路径
 给定一个二叉树，返回所有从根节点到叶子节点的路径。

 说明: 叶子节点是指没有子节点的节点。

 示例:

 输入:

    1
  /   \
 2     3
  \
   5

 输出: ["1->2->5", "1->3"]

 解释: 所有根节点到叶子节点的路径为: 1->2->5, 1->3
 */

class BinaryTreePaths: NSObject {
    
    var resultArr:[String] = []
    
    func binaryTreePaths(_ root: TreeNode?) -> [String] {
        guard root != nil else {
            return []
        }
        
        self.dfs(root!, "\(root!.val)")
        
        return resultArr
    }
    
    //深度优先搜索解法
    func dfs(_ root: TreeNode?, _ currentString: String){
        if root?.left == nil && root?.right == nil{
            resultArr.append(currentString)
            return
        }
        let str = "\(currentString)->"
        
        if root?.left != nil {
            self.dfs(root!.left, "\(str)\(root!.left!.val)")
        }
        if root?.right != nil {
            self.dfs(root!.right, "\(str)\(root!.right!.val)")
        }
    }
    
}
